package graph;

import org.omg.CORBA.PUBLIC_MEMBER;
import unionfindset.UnionFindSet;

import java.awt.*;
import java.util.*;

/**
 * @Author 12629
 * @Description： 使用邻接矩阵来存储图
 */
public class GraphByMatrix {

    private char[] arrayV;//顶点数组
    private int[][] matrix;//矩阵
    private boolean isDirect;//是否是有向图

    /**
     * 此时
     * @param size 代表当前顶点的个数
     * @param isDirect
     */
    public GraphByMatrix(int size,boolean isDirect) {
        this.arrayV = new char[size];
        matrix = new int[size][size];
        for (int i = 0; i < size; i++) {
            Arrays.fill(matrix[i],Constant.MAX);
        }
        this.isDirect = isDirect;
    }

    public void initArrayV(char[] array) {
        for (int i = 0; i < array.length; i++) {
            arrayV[i] = array[i];
        }
    }

    /**
     *
     * @param srcV 起点
     * @param destV 终点
     * @param weight 权值
     */
    public void addEdge(char srcV,char destV,int weight) {
        int srcIndex = getIndexOfV(srcV);
        int destIndex = getIndexOfV(destV);
        matrix[srcIndex][destIndex] = weight;
        //如果是无向图 那么相反的位置 也同样需要置为空
        if(!isDirect) {
            matrix[destIndex][srcIndex] = weight;
        }
    }

    /**
     * 获取顶点V的下标
     * @param v
     * @return
     */
    private int getIndexOfV(char v) {
        for (int i = 0; i < arrayV.length; i++) {
            if(arrayV[i] == v) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 获取顶点的度：有向图 = 入度+出度
     * @param v
     * @return
     */
    public int getDevOfV(char v) {
        int count = 0;

        int srcIndex = getIndexOfV(v);

        for (int i = 0; i < arrayV.length; i++) {
            if(matrix[srcIndex][i] != Constant.MAX) {
                count++;
            }
        }

        //计算有向图的入度
        if(isDirect) {
            for (int i = 0; i <  arrayV.length; i++) {
                if(matrix[i][srcIndex] != Constant.MAX) {
                    count++;
                }
            }
        }
        return count;
    }

    public void printGraph() {
        for (int i = 0; i < arrayV.length; i++) {
            System.out.print(arrayV[i]+" ");
        }
        System.out.println();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                if(matrix[i][j] == Constant.MAX) {
                    System.out.print("∞ ");
                }else {
                    System.out.print(matrix[i][j]+" ");
                }
            }
            System.out.println();
        }
    }


    public void bfs(char v) {
        //1、定义一个visited数组 标记当前这个顶点是不是已经被 访问的
        boolean[] visited = new boolean[arrayV.length];
        //2、定义一个队列，来辅助完成广度优先遍历
        Queue<Integer> queue = new LinkedList<>();
        int srcIndex = getIndexOfV(v);
        queue.offer(srcIndex);
        while (!queue.isEmpty()) {
            int top = queue.poll();
            System.out.print(arrayV[top]+"->");
            visited[top] = true;//每次弹出一个元素 就置为true
            for (int i = 0; i < arrayV.length; i++) {
                if(matrix[top][i] != Constant.MAX && !visited[i]) {
                    queue.offer(i);
                    visited[i] = true;
                }
            }
        }
    }

    /**
     * 深度优先遍历
     * @param v
     */
    public void dfs(char v) {
        boolean[] visited = new boolean[arrayV.length];
        int srcIndex = getIndexOfV(v);
        dfsChild(srcIndex,visited);

    }

    private void dfsChild(int srcIndex,boolean[] visited) {
        System.out.print(arrayV[srcIndex]+"->");
        visited[srcIndex] = true;

        for (int i = 0; i < arrayV.length; i++) {
            if(matrix[srcIndex][i] != Constant.MAX && !visited[i]) {
                dfsChild(i,visited);
            }
        }
    }


    /**
     * 定义了一个边的抽象类
     */
    static class Edge {
        public int srcIndex;
        public int destIndex;
        public int weight;//权重

        public Edge(int srcIndex, int destIndex, int weight) {
            this.srcIndex = srcIndex;
            this.destIndex = destIndex;
            this.weight = weight;
        }
    }
    /**
     * 克鲁斯卡尔算法 实现
     * @param minTree
     * @return
     */
    public int kruskal(GraphByMatrix minTree) {
        //1、定义一个优先级队列 用来存储边
        PriorityQueue<Edge> minQ = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });

        int n = arrayV.length;//顶点的个数
        //2. 遍历邻接矩阵，把所有的边，放到优先级队列当中
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(i < j && matrix[i][j] != Constant.MAX) {
                    minQ.offer(new Edge(i,j,matrix[i][j]));
                }
            }
        }
        UnionFindSet ufs = new UnionFindSet(n);
        //3、开始从 优先级队列当中 取边
        int size = 0;
        int totalWight = 0;
        while (size < n-1 && !minQ.isEmpty()) {
            Edge edge = minQ.poll();
            int srcIndex = edge.srcIndex;
            int destIndex = edge.destIndex;

            if(!ufs.isSameUnionFindSet(srcIndex,destIndex)) {
                //添加到最小生成树当中
                minTree.addEdgeUseIndex(srcIndex,destIndex,matrix[srcIndex][destIndex]);
                System.out.println("选择的边："+arrayV[srcIndex]+"->"+
                        arrayV[destIndex]+":"+matrix[srcIndex][destIndex]);
                size++;//记录添加的边的条数
                totalWight+= matrix[srcIndex][destIndex];//记录最小生成树的 权值
                ufs.union(srcIndex,destIndex);
            }
        }

        if(size == n-1) {
            return totalWight;
        }else {
            return -1;//没有最小生成树
        }
    }

    private void addEdgeUseIndex(int srcIndex,int destIndex,int weight) {
        matrix[srcIndex][destIndex] = weight;
        //如果是无向图 那么相反的位置 也同样需要置为空
        if(!isDirect) {
            matrix[destIndex][srcIndex] = weight;
        }
    }

    public static void testGraphMinTree() {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),false);
        g.initArrayV(array);

        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
        //g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);

        GraphByMatrix  kminTree = new GraphByMatrix(str.length(),false);
        System.out.println(g.kruskal(kminTree));
        kminTree.printGraph();
    }


    //起点
    public  int prim(GraphByMatrix minTree,char chV) {
        int srcIndex = getIndexOfV(chV);
        //存储已经确定的点
        Set<Integer> setX = new HashSet<>();
        //先把确定的顶点放到集合当中
        setX.add(srcIndex);

        //初始化Y集合 ，存储的是 未确定的顶点
        Set<Integer> setY = new HashSet<>();
        int n = arrayV.length;
        for (int i = 0; i < n; i++) {
            if(i != srcIndex) {
                setY.add(i);
            }
        }

        //定义一个优先级队列
        PriorityQueue<Edge> minQ = new PriorityQueue<>(new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });

        //遍历srcIndex连接出去的所边
        for (int i = 0; i < n; i++) {
            if(matrix[srcIndex][i] != Constant.MAX) {
                minQ.offer(new Edge(srcIndex,i,matrix[srcIndex][i]));
            }
        }

        int size = 0;
        int totalWeight = 0;
        //遍历优先级队列，取出n-1条边
        while (!minQ.isEmpty()) {
            Edge min = minQ.poll();
            int srcI = min.srcIndex;
            int desT = min.destIndex;

            if(setX.contains(desT)) {
                //构成环
                System.out.println("构成环的边："+arrayV[srcI]+"->"+
                        arrayV[desT]+":"+matrix[srcI][desT]);
            }else {
                minTree.addEdgeUseIndex(srcI,desT,min.weight);

                System.out.println("选择的边："+arrayV[srcI]+"->"+
                        arrayV[desT]+":"+matrix[srcI][desT]);

                totalWeight += min.weight;
                size++;
                if(size == n-1) {
                   return totalWeight;
                }
                //更新两个集合的
                setX.add(desT);
                setY.remove(desT);

                //把destI连接出去的所有边，也放到优先级队列当中
                for (int i = 0; i < n; i++) {
                    if(matrix[desT][i] != Constant.MAX && !setX.contains(i)) {
                        minQ.offer(new Edge(desT,i,matrix[desT][i]));
                    }
                }
            }
        }
        return -1;
    }

    public static void testGraphMinTreePrim() {
        String str = "abcdefghi";
        char[] array =str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),false);
        g.initArrayV(array);

        g.addEdge('a', 'b', 4);
        g.addEdge('a', 'h', 8);
        //g.addEdge('a', 'h', 9);
        g.addEdge('b', 'c', 8);
        g.addEdge('b', 'h', 11);
        g.addEdge('c', 'i', 2);
        g.addEdge('c', 'f', 4);
        g.addEdge('c', 'd', 7);
        g.addEdge('d', 'f', 14);
        g.addEdge('d', 'e', 9);
        g.addEdge('e', 'f', 10);
        g.addEdge('f', 'g', 2);
        g.addEdge('g', 'h', 1);
        g.addEdge('g', 'i', 6);
        g.addEdge('h', 'i', 7);

        GraphByMatrix  primTree = new GraphByMatrix(str.length(),false);
        System.out.println(g.prim(primTree,'a'));
        primTree.printGraph();

    }


    /**
     *
     * @param vSrc 指定的起点
     * @param dist 距离数组
     * @param pPath 路径
     */
    public void dijkstra(char vSrc,int[] dist,int[] pPath) {
        int srcIndex = getIndexOfV(vSrc);
        //距离数据初始化
        Arrays.fill(dist,Constant.MAX);
        dist[srcIndex] = 0;
        //路径数组初始化
        Arrays.fill(pPath,-1);
        pPath[srcIndex] = 0;
        //当前顶点是否被访问过？
        int n = arrayV.length;
        boolean[] s = new boolean[n];

        //n个顶点,要更新n次，每次都要从0下标开始，找到一个最小值
        for (int k = 0; k < n; k++) {
            int min = Constant.MAX;
            int u = srcIndex;
            for (int i = 0; i < n; i++) {
                if(s[i] == false && dist[i] < min) {
                    min = dist[i];
                    u = i;//更新u下标
                }
            }
            s[u] = true;//u:s
            //松弛u连接出去的所有的顶点 v
            for (int v = 0; v < n; v++) {
                if(s[v] == false && matrix[u][v] != Constant.MAX
                && dist[u] + matrix[u][v] < dist[v]) {
                    dist[v] = dist[u] + matrix[u][v];
                    pPath[v] = u;//更新当前的路径
                }
            }
        }
    }

    public void printShortPath(char vSrc,int[] dist,int[] pPath) {
        int srcIndex = getIndexOfV(vSrc);

        int n = arrayV.length;

        for (int i = 0; i < n; i++) {
            //i下标正好是起点  则不进行路径的打印
            if(i != srcIndex) {
                ArrayList<Integer> path = new ArrayList<>();
                int pathI = i;
                while (pathI != srcIndex) {
                    path.add(pathI);
                    pathI = pPath[pathI];
                }
                path.add(srcIndex);

                Collections.reverse(path);

                for (int pos : path) {
                    System.out.print(arrayV[pos]+" -> ");
                }
                System.out.println(dist[i]);
            }
        }
    }

    public static void testGraphDijkstra() {
        /*String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
        g.addEdge('s', 't', 10);
        g.addEdge('s', 'y', 5);
        g.addEdge('y', 't', 3);
        g.addEdge('y', 'x', 9);
        g.addEdge('y', 'z', 2);
        g.addEdge('z', 's', 7);
        g.addEdge('z', 'x', 6);
        g.addEdge('t', 'y', 2);
        g.addEdge('t', 'x', 1);
        g.addEdge('x', 'z', 4);*/

        /*
        搞不定负权值*/
        String str = "sytx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
        g.addEdge('s', 't', 10);
        g.addEdge('s', 'y', 5);
        g.addEdge('t', 'y', -7);
        g.addEdge('y', 'x', 3);

        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        g.dijkstra('s', dist, parentPath);

        System.out.println("dasfa");
        g.printShortPath('s', dist, parentPath);
    }


    public boolean bellmanFord(char vSrc,int[] dist,int[] pPath) {
        int srcIndex = getIndexOfV(vSrc);
        //距离数据初始化
        Arrays.fill(dist,Constant.MAX);
        dist[srcIndex] = 0;
        //路径数组初始化
        Arrays.fill(pPath,-1);
        pPath[srcIndex] = 0;

        int n = arrayV.length;

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(matrix[i][j] != Constant.MAX &&
                    dist[i] + matrix[i][j] < dist[j]) {
                        dist[j] = dist[i] + matrix[i][j];
                        pPath[j] = i;
                    }
                }
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] != Constant.MAX &&
                        dist[i] + matrix[i][j] < dist[j]) {
                   return false;
                }
            }
        }
        return true;
    }

    public static void testGraphBellmanFord() {
        String str = "syztx";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
        g.addEdge('s', 't', 6);
        g.addEdge('s', 'y', 7);
        g.addEdge('y', 'z', 9);
        g.addEdge('y', 'x', -3);
        g.addEdge('z', 's', 2);
        g.addEdge('z', 'x', 7);
        g.addEdge('t', 'x', 5);
        g.addEdge('t', 'y', 8);
        g.addEdge('t', 'z', -4);
        g.addEdge('x', 't', -2);

        //负权回路实例
       /* g.addEdge('s', 't', 6);
        g.addEdge('s', 'y', 7);
        g.addEdge('y', 'z', 9);
        g.addEdge('y', 'x', -3);
        g.addEdge('y', 's', 1);
        g.addEdge('z', 's', 2);
        g.addEdge('z', 'x', 7);
        g.addEdge('t', 'x', 5);
        g.addEdge('t', 'y', -8);
        g.addEdge('t', 'z', -4);
        g.addEdge('x', 't', -2);*/

        int[] dist = new int[array.length];
        int[] parentPath = new int[array.length];
        boolean flg = g.bellmanFord('s', dist, parentPath);
        if(flg) {
            g.printShortPath('s', dist, parentPath);
        }else {
            System.out.println("存在负权回路");
        }
    }


    public void floydWarShall(int[][] dist,int[][] pPath) {
        int n = arrayV.length;

        for (int i = 0; i < n; i++) {
            Arrays.fill(dist[i],Constant.MAX);
            Arrays.fill(pPath[i],-1);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if(matrix[i][j] != Constant.MAX) {
                    dist[i][j] = matrix[i][j];
                    pPath[i][j] = i;
                }else {
                    pPath[i][j] = -1;
                }
                if(i == j) {
                    dist[i][j] = 0;
                    pPath[i][j] = -1;
                }
            }
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(dist[i][k] != Constant.MAX &&
                            dist[k][j] != Constant.MAX &&
                            dist[i][k] + dist[k][j] < dist[i][j]) {
                        dist[i][j] = dist[i][k] + dist[k][j];
                        //更新父节点下标
                        //pPath[i][j] = k;//不对
                        //如果经过了 i->k  k->j  此时是k
                        //i->x->s->k   k->..t->...x->j
                        pPath[i][j] = pPath[k][j];
                    }
                }
            }
            // 测试 打印权值和路径矩阵观察数据
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if(dist[i][j] == Constant.MAX) {
                        System.out.print(" * ");
                    }else{
                        System.out.print(dist[i][j]+" ");
                    }
                }
                System.out.println();
            }
            System.out.println("=========打印路径==========");
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    System.out.print(pPath[i][j]+" ");
                }
                System.out.println();
            }
            System.out.println("=================");
        }
    }

    public static void testGraphFloydWarShall() {
        String str = "12345";
        char[] array = str.toCharArray();
        GraphByMatrix g = new GraphByMatrix(str.length(),true);
        g.initArrayV(array);
        g.addEdge('1', '2', 3);
        g.addEdge('1', '3', 8);
        g.addEdge('1', '5', -4);
        g.addEdge('2', '4', 1);
        g.addEdge('2', '5', 7);
        g.addEdge('3', '2', 4);
        g.addEdge('4', '1', 2);
        g.addEdge('4', '3', -5);
        g.addEdge('5', '4', 6);

        int[][] dist = new int[array.length][array.length];
        int[][] parentPath = new int[array.length][array.length];
        g.floydWarShall(dist,parentPath);

        for (int i = 0; i < array.length; i++) {
            g.printShortPath(array[i],dist[i],parentPath[i]);
            System.out.println("************************");
        }
    }

    public static void main(String[] args) {
        testGraphFloydWarShall();
    }

    public static void main1(String[] args) {

        GraphByMatrix graph = new GraphByMatrix(4,false);
        char[] array = {'A','B','C','D'};
        graph.initArrayV(array);

        graph.addEdge('A','B',1);
        graph.addEdge('A','D',1);
        graph.addEdge('B','A',1);
        graph.addEdge('B','C',1);
        graph.addEdge('C','B',1);
        graph.addEdge('C','D',1);
        graph.addEdge('D','A',1);
        graph.addEdge('D','C',1);

        //graph.bfs('B');
        graph.dfs('B');
        //graph.printGraph();
        //System.out.println(graph.getDevOfV('A'));
    }

}
